{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# C语言指针链表实训课程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 任务描述\n",
    "\n",
    "        本关要求按照数据输入的顺序构建一个线性表。即如果输入的 3 个结点数据分别为 1 、 2 、 3 ，则构建的线性表包含 3 个结点，且从前往后的结点数据分别为 1 、 2 、 3 。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 相关知识\n",
    "\n",
    "        线性表（linear list）是一种数据结构，是由 n 个具有相同特性的数据元素构成的序列。线性表中元素的个数 n 即为线性表的长度，当 n = 0 时称为空表。线性表的相邻元素之间存在着序偶关系。如用（a[0]，…，a[i-1]，a[i]，a[i+1]，…，a[n-1]）表示一个线性表，则称a[i-1]是a[i]的前驱，a[i+1]是a[i]的后继。\n",
    "\n",
    "### 线性表的特性\n",
    "\n",
    "        *线性表中必存在唯一的一个“第一元素”；\n",
    "        *线性表中必存在唯一的一个 “最后元素” ；\n",
    "        *除最后一个元素之外，均有唯一的后继；\n",
    "        *除第一个元素之外，均有唯一的前驱。\n",
    "\n",
    "### 线性表的一般操作\n",
    "\n",
    "        *将线性表变为空表；\n",
    "        *返回线性表的长度，即表中元素个数；\n",
    "        *获取线性表某位置的元素；\n",
    "        *定位某个元素在线性表中的位置；\n",
    "        *在线性表中插入一个元素；\n",
    "        *删除某个元素；\n",
    "        *判断线性表是否为空；\n",
    "        *遍历输出线性表的所有元素；\n",
    "        *线性表排序。\n",
    "\n",
    "### 线性表的链表表示\n",
    "\n",
    "        线性表可以用链表来实现。链表是通过指针链接在一起的一组数据项（结点）。链表的每个结点都是同类型的结构，该结构中一般包含两类信息:\n",
    "            *一类称为数据域，存储业务相关的数据（如财务系统的数据域为财务信息，车辆管理系统的业务信息为车辆信息）;\n",
    "            *另一类称为指针域，用于构建结点的链接关系。单链表的实现只需要一个指针。\n",
    "\n",
    "        要实现上述链表，只需要定义如下结构：\n",
    "        定义结点结构\n",
    "        struct node\n",
    "        {\n",
    "            int data;  // 数据域\n",
    "            node * next;  // 指针域,指向下一个结点\n",
    "        };\n",
    "\n",
    "        如下程序可以构建上述图中链表（其中：每个结点都是node类型的一个结构变量，head则是node*类型的指针）：\n",
    "\n",
    "        node a, b, c, d, *head;\n",
    "        head = &a;     // 让head指针指向结点a\n",
    "        a.data = 28;   // 给a的数据域赋值\n",
    "        a.next = &b;   // 让a的指针域指向结点b\n",
    "        b.data = 52;   // 给b的数据域赋值\n",
    "        b.next = &c;   // 让b的指针域指向结点c\n",
    "        c.data = 2;    // 给c的数据域赋值\n",
    "        c.next = &d;   // 让c的指针域指向结点d\n",
    "        d.data = 96;   // 给d的数据域赋值\n",
    "        d.next = NULL; //给d的指针域置为NULL，表示后面没有结点了\n",
    "\n",
    "        很显然，这样写程序比较麻烦，而且在不知道有多少结点的情况下也根本无法处理。怎么可以解决这个问题呢？ C 和 C++ 的内存动态分配方法可以很好的解决这个问题。\n",
    "        C++ 提供了两种动态分配内存的方法：\n",
    "            *一种是 C 语言提供的malloc和free函数；\n",
    "            *一种是 C++ 扩展的new和delete运算符。\n",
    "        C 语言提供的动态内存方法（malloc和free函数）代码如下：\n",
    "\n",
    "        node *t = (node *)malloc(sizeof(node));\n",
    "        t->data = 2;\n",
    "        free(t);\n",
    "\n",
    "        接下来，使用动态内存分配的方法实现上述的单链表的代码如下：\n",
    "\n",
    "        node *head, *t, *p;\n",
    "        t = new node;   // 动态分配一个node结点的空间，并让t指向它\n",
    "        head = t;       // 该结点是第一个结点，让head指向它\n",
    "        t->data = 28;   // 给第一个结点的数据域赋值\n",
    "        p = new node;   // 动态分配第二个node结点的空间，并让p指向它\n",
    "        t->next = p;    // 修改第一个结点的指针域为第二个结点的地址（第一个结点的指针域指向第二个结点）\n",
    "        p->data = 52;   // 给第二个结点的数据域赋值\n",
    "        t=p;            // 让t指向最后一个结点\n",
    "        p = new node;   // 动态分配第三个node结点的空间，并让p指向它（p不再指向第二个结点了）\n",
    "        t->next = p;    // 修改第二个结点的指针域为第三个结点的地址（第二个结点的指针域指向第三个结点）\n",
    "        p->data = 2;    // 给第三个结点的数据域赋值\n",
    "        t = p;          // 让t指向最后一个结点\n",
    "        p = new node;   // 动态分配第四个node结点的空间，并让p指向它（p不再指向第三个结点了）\n",
    "        t->next = p;    // 修改第三个结点的指针域为第四个结点的地址（第三个结点的指针域指向第四个结点）\n",
    "        p->data = 96;   // 给第四个结点的数据域赋值\n",
    "        p->next = NULL; // 给第四个结点的指针域置为NULL，表示后面没有结点了\n",
    "\n",
    "        上述程序语句虽然好像变多了，程序也好像变复杂了，但细读会发现这段程序可以很方便地改成循环，这样处理后其实是使得程序更简单了，并且适用于任意多个结点的情况。\n",
    "        改成循环后，单链表里面可能包含 0 个或多个结点，如果包含多个结点，则下面程序中的语句可以让指针t指向链表的最后一个结点，具体代码如下：\n",
    "\n",
    "        node *t = head; // t指向第一个结点\n",
    "\n",
    "        如果t->next不为NULL，即后面还有结点\n",
    "        while(t->next != NULL)\n",
    "        {\n",
    "            t = t->next;  // 把t指向结点的指针域（下一个结点地址）赋值给t，t指向下一个结点\n",
    "        }\n",
    "        循环结束时，t->next为NULL，即t指向的结点后面没有结点了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 编程要求\n",
    "\n",
    "        本关的编程任务是补全insertTail函数、printList函数、delList函数以及main函数，以实现顺序构建线性表的要求。具体要求如下：\n",
    "        本关要求重点补全insertTail函数和main函数，其中insertTail函数的返回值为插入结点后链表的首结点地址；\n",
    "        具体请参见后续测试样例。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测试说明\n",
    "\n",
    "        下面是对平台如何评测你的样例测试。\n",
    "        测试输入：\n",
    "        5\n",
    "        1 2 3 4 5\n",
    "        预期输出：\n",
    "        List: 1 2 3 4 5\n",
    "        测试输入：\n",
    "        3\n",
    "        8 7 6\n",
    "        预期输出：\n",
    "        List: 8 7 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实训区域"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <stdio.h>\n",
    "\n",
    "// 定义结点结构\n",
    "struct node\n",
    "{\n",
    "    int data;  // 数据域\n",
    "    struct node * next;  //指针域,指向下一个结点\n",
    "};\n",
    "\n",
    "\n",
    "/* 函数insertTail：链表尾部插入\n",
    "   参数：h-链表头指针，t-指向要插入的结点\n",
    "   返回值：插入结点后链表的首结点地址*/\n",
    "struct node *insertTail(struct node *h, struct node *t)\n",
    "{\n",
    "    // 请在此添加代码，补全函数insertTail\n",
    "    /********** Begin *********/\n",
    "\n",
    "\n",
    "    /********** End **********/\n",
    "}\n",
    "\n",
    "/* 函数printList：输出链表，每个数据之间用一个空格隔开\n",
    "   参数：h-链表头指针*/\n",
    "void printList(struct node *h)\n",
    "{\n",
    "    // 请在此添加代码，补全函数printList\n",
    "    /********** Begin *********/\n",
    "\n",
    "\n",
    "    /********** End **********/\n",
    "}\n",
    "\n",
    "/* 函数delList：删除链表，释放空间\n",
    "   参数：h-链表头指针*/\n",
    "void delList(struct node *h)\n",
    "{\n",
    "    // 请在此添加代码，补全函数delList\n",
    "    /********** Begin *********/\n",
    "\n",
    "\n",
    "    /********** End **********/\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    // 请在此添加代码，补全函数main\n",
    "    /********** Begin *********/\n",
    "    \n",
    "    \n",
    "    /********** End **********/\n",
    "    return 0;\n",
    "}\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C",
   "language": "c",
   "name": "c"
  },
  "language_info": {
   "file_extension": ".c",
   "mimetype": "text/plain",
   "name": "c"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
